package com.ycy.leetcode.dongtaiguihua;

import java.util.Arrays;

/**
 * 编辑距离
 */
public class BianJiJuli {

  public static void main(String[] args) {
    int[][] test = test("h", "he");
    int length = test.length;
    for (int i = 0; i < length; i++) {
      System.out.println(Arrays.toString(test[i]));
    }
  }

  public static int[][] test(String aWord, String bWord) {

    int aWordLen = aWord.length() + 1;
    int bWordLen = bWord.length() + 1;
    // 定义状态方程 arr[i][j] 表示 a单词中前i个字母转化成 b单词中前j个字母，需要的最小操作次数
    int arr[][] = new int[aWordLen][bWordLen];
    for (int i = 0; i < aWordLen; i++) {
      arr[i][0] = i;
    }
    for (int i = 0; i < bWordLen; i++) {
      arr[0][i] = i;
    }

    for (int i = 1; i < aWordLen; i++) {
      for (int j = 1; j < bWordLen; j++) {
        if (aWord.charAt(i - 1) == bWord.charAt(j - 1)) {
          arr[i][j] = 1 + arr[i - 1][j - 1];
        } else {
          arr[i][j] = 1 + Math.min(Math.min(arr[i - 1][j], arr[i][j - 1]), arr[i - 1][j - 1]);
        }
      }
    }

    return arr;

  }

}
